package 迷宫问题3;

public class 迷宫问题 {
    //定义两个一维数组方便表示右，上，左，下四个方向
    static int[] dirX={1,0,-1,0};
    static int[] dirY={0,1,0,-1};
    //初始化一个二维数组
    static int[][] m={
               {0,1,0,0,0}
              ,{0,1,0,1,0}
              ,{0,0,0,0,0}
              ,{0,1,1,1,0}
              ,{0,0,0,1,0}};
    static int[][] t=new int[5][5];

    public static void main(String[] args) {
        t[0][0]=1;
        f(0,0);
        printArr();
    }

    /**
     *
     * @param x 数组的行
     * @param y 数组的列
     */
    public static void f(int x,int y){
        if(x==4&&y==4){//如果是迷宫的右下角（出口)
            printArr();
            return;
        }
        for (int i = 0; i < 4; i++) {
            int newX=x+dirX[i];
            int newY=y+dirY[i];
            //如果该点在迷宫中并且可以走(不是障碍)并且没有访问过
            if(newX>=0&&newX<=4&&newY>=0&&newY<=4&&t[newX][newY]==0&&m[newX][newY]==0){
                t[newX][newY]=1;//先将这个点设为1
                f(newX,newY);//DFS深搜
                t[newX][newY]=0;//回溯 状态换回来，不影响下一次访问

            }

        }

    }
    public static void printArr(){
        for (int i = 0; i <5 ; i++) {
            for (int j = 0; j <5 ; j++) {
                System.out.print(t[i][j]+" ");
            }
            System.out.println();
        }
        System.out.println("^_^^_^^_^^_^^_^^_^^_^^_^^_^^_^");

    }

}
